package com.leetcode.algorithm.y18.m06;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * leetcode-cn.com
 * (done)697. 数组的度
 * (done)717. 1比特与2比特字符
 * (done)724. 寻找数组的中心索引
 * (done)747. 至少是其他数字两倍的最大数
 * (done)766. 托普利茨矩阵
 * (done)830. 较大分组的位置
 * (done)840. 矩阵中的幻方 
 * @author: dengjie213@126.com
 * @time: 2018年6月9日 下午12:28:38
 */
public class MySolution0609 {
	
    /**
     * 697. 数组的度
     * 给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
     * 你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
     * 
     * 示例 1:
     * 输入: [1, 2, 2, 3, 1]
     * 输出: 2
     * 解释: 
     * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
     * 连续子数组里面拥有相同度的有如下所示:
     * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     * 最短连续子数组[2, 2]的长度为2，所以返回2.
     * 
     * 示例 2:
     * 输入: [1,2,2,3,1,4,2]
     * 输出: 6
     * 
     * 注意:
     * nums.length 在1到50,000区间范围内。
     * nums[i] 是一个在0到49,999范围内的整数。
     * @param nums
     * @return
     */
	public int findShortestSubArray(int[] nums) {
		int len = nums.length;
		int maxCnt = 1; // 出现频数的最大值
		HashMap<Integer, Integer> cntMap = new HashMap<Integer, Integer>();// K为nums[i]，V为出现频数
		List<Integer> list = new ArrayList<Integer>(); // 出现频数等于出现频数最大值的nums[i]的集合
		for (int i = 0; i < len; i++) {
			Integer cnt = cntMap.get(nums[i]);
			if (cnt == null) {
				cntMap.put(nums[i], 1);
			} else {
				cnt++;
				cntMap.put(nums[i], cnt);
				if (cnt > maxCnt) {
					maxCnt = cnt;
					list.clear();
					list.add(nums[i]);
				} else if (cnt == maxCnt) {
					list.add(nums[i]);
				}
			}
		}
		if (maxCnt == 1) {
			return 1;
		}
		int lenMin = len;
		for (Integer num : list) {
			int i = 0;
			while (i < len && num != nums[i]) {
				i++;
			}
			int j = len - 1;
			while (j >= 0 && num != nums[j]) {
				j--;
			}
			if (lenMin > (j + 1 - i)) {
				lenMin = j + 1 - i;
			}
		}

		return lenMin;
	}
    
    /**
     * 717. 1比特与2比特字符
     * 有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
     * 现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。
     * 给定的字符串总是由0结束。
     * 
     * 示例 1:
     * 输入: 
     * bits = [1, 0, 0]
     * 输出: True
     * 解释: 
     * 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
     * 
     * 示例 2:
     * 输入: 
     * bits = [1, 1, 1, 0]
     * 输出: False
     * 解释: 
     * 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
     * 
     * 注意:
     * 1 <= len(bits) <= 1000.
     * bits[i] 总是0 或 1.
     * @param bits
     * @return
     */
	public boolean isOneBitCharacter(int[] bits) {
		int len = bits.length;
		if (len == 1) {
			return true;
		}
		int i = len - 1 - 1; // 从倒数第二个数开始，找到第一个0
		while (i >= 0 && bits[i] != 0) {
			i--;
		}
		// bits索引[i+1,len-1-1]均为1
		return (len - 1 - (i + 1)) % 2 == 0;
	}
    
    
    /**
     * 724. 寻找数组的中心索引
     * 给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。
     * 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
     * 
     * 示例 1:
     * 输入: 
     * nums = [1, 7, 3, 6, 5, 6]
     * 输出: 3
     * 解释: 
     * 索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
     * 同时, 3 也是第一个符合要求的中心索引。
     * 
     * 示例 2:
     * 输入: 
     * nums = [1, 2, 3]
     * 输出: -1
     * 解释: 
     * 数组中不存在满足此条件的中心索引。
     * 
     * 说明:
     * nums 的长度范围为 [0, 10000]。
     * 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
     * @param nums
     * @return
     */
	public int pivotIndex(int[] nums) {
		int len = nums.length;
		if (len == 0) {
			return -1;
		}
		int idx = 0;
		int sumL = 0;
		int sumR = 0;
		for (int i = 1; i < len; i++) {
			sumR += nums[i];
		}
		if (sumR == sumL) {
			return idx;
		}
		for (idx = 1; idx < len; idx++) {
			sumL += nums[idx - 1];
			sumR -= nums[idx];
			if (sumR == sumL) {
				return idx;
			}
		}
		return -1;
	}

    /**
     * 747. 至少是其他数字两倍的最大数
     * 在一个给定的数组nums中，总是存在一个最大元素 。
     * 查找数组中的最大元素是否至少是数组中每个其他数字的两倍。
     * 如果是，则返回最大元素的索引，否则返回-1。
     * 
     * 示例 1:
     * 输入: nums = [3, 6, 1, 0]
     * 输出: 1
     * 解释: 6是最大的整数, 对于数组中的其他整数,
     * 6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.
     *  
     * 示例 2:
     * 输入: nums = [1, 2, 3, 4]
     * 输出: -1
     * 解释: 4没有超过3的两倍大, 所以我们返回 -1.
     * 
     * 提示:
     * nums 的长度范围在[1, 50].
     * 每个 nums[i] 的整数范围在 [0, 99].
     * @param nums
     * @return
     */
	public int dominantIndex(int[] nums) {
		int len = nums.length;
		if (len == 1) {
			return 0;
		}
		int maxIdx = -1;
		int max1 = Integer.MIN_VALUE;
		int max2 = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > max2) {
				if (nums[i] > max1) {
					maxIdx = i;
					max2 = max1;
					max1 = nums[i];
				} else if (nums[i] != max1) {
					max2 = nums[i];
				}
			}
		}
		if (maxIdx >= 0) {
			return max1 >= (max2 << 1) ? maxIdx : -1;
		}
		return maxIdx;
	}
    
    /**
     * 766. 托普利茨矩阵
     * 如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。
     * 给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
     * 
     * 示例 1:
     * 输入: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
     * 输出: True
     * 解释:
     * 1234
     * 5123
     * 9512
     * 在上面这个矩阵中, 对角线分别是 "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", 各条对角线上的所有元素都相同, 因此答案是True。
     * 
     * 示例 2:
     * 输入: matrix = [[1,2],[2,2]]
     * 输出: False
     * 解释: 
     * 对角线, 比如: "[1, 2]" 上有不同的元素。
     * 注意:
     *  matrix (矩阵)是一个包含整数的二维数组。
     * 	matrix 的行数和列数均在 [1, 20]范围内。
     * 	matrix[i][j] 包含的整数在 [0, 99]范围内。
     * @param matrix
     * @return
     */
	public boolean isToeplitzMatrix(int[][] matrix) {
		int row = matrix.length;
		int col = matrix[0].length;
		for (int i = 0; i <= row - 2; i++) {
			for (int j = 0; j <= col - 2; j++) {
				if (matrix[i][j] != matrix[i + 1][j + 1]) {
					return false;
				}
			}
		}
		return true;
	}
    
    /**
     * 830. 较大分组的位置
     * 在一个由小写字母构成的字符串 S 中，包含由一些连续的相同字符所构成的分组。
     * 例如，在字符串 S = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。
     * 我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。
     * 最终结果按照字典顺序输出。
     * 
     * 示例 1:
     * 输入: "abbxxxxzzy"
     * 输出: [[3,6]]
     * 解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。
     * 
     * 示例 2:
     * 输入: "abc"
     * 输出: []
     * 解释: "a","b" 和 "c" 均不是符合要求的较大分组。
     * 
     * 示例 3:
     * 输入: "abcdddeeeeaabbbcd"
     * 输出: [[3,5],[6,9],[12,14]]
     * 说明:  1 <= S.length <= 1000
     * @param S
     * @return
     */
	public List<List<Integer>> largeGroupPositions(String S) {
		List<List<Integer>> list = new ArrayList<>();
		int len = S.length();
		if (len < 3) {
			return list;
		}
		int cnt = 0;
		int i = 1;
		while (i < len) {
			if (S.charAt(i) == S.charAt(i - 1)) {
				cnt++;
			} else {
				if (cnt >= 2) {
					list.add(Arrays.asList(i - 1 - cnt, i - 1));
				}
				cnt = 0;
			}
			i++;
		}
		if (cnt >= 2) {
			list.add(Arrays.asList(i - 1 - cnt, i - 1));
		}
		return list;
	}
    
    /**
     * 840. 矩阵中的幻方
     * 3 x 3 的幻方是一个填充有从 1 到 9 的不同数字的 3 x 3 矩阵，其中每行，每列以及两条对角线上的各数之和都相等。
     * 给定一个由整数组成的 N × N 矩阵，其中有多少个 3 × 3 的 “幻方” 子矩阵？（每个子矩阵都是连续的）。
     * 
     * 示例 1:
     * 输入: [[4,3,8,4],
     *       [9,5,1,9],
     *       [2,7,6,2]]
     * 输出: 1
     * 解释: 
     * 下面的子矩阵是一个 3 x 3 的幻方：
     * 438
     * 951
     * 276
     * 
     * 而这一个不是：
     * 384
     * 519
     * 762
     * 
     * 总的来说，在本示例所给定的矩阵中只有一个 3 x 3 的幻方子矩阵。
     * 提示:
     * 1 <= grid.length = grid[0].length <= 10
     * 0 <= grid[i][j] <= 15
     * @param grid
     * @return
     */
	public int numMagicSquaresInside(int[][] grid) {
		int cnt = 0;
		int lenR = grid.length;
		int lenC = grid[0].length;
		for (int i = 1; i < lenR - 1; i++) {
			for (int j = 1; j < lenC - 1; j++) {
				if (grid[i][j] == 5) {
					if ((grid[i - 1][j] + grid[i + 1][j] == 10) //j列
							&& (grid[i - 1][j - 1] + grid[i + 1][j + 1] == 10)//对角线
							&& (grid[i - 1][j + 1] + grid[i + 1][j - 1] == 10)//对角线
							&& (grid[i][j - 1] + grid[i][j + 1] == 10)//i行
							&& (grid[i-1][j-1] + grid[i-1][j + 1] + grid[i-1][j] == 15)//i-1行
							&& (grid[i+1][j-1] + grid[i+1][j + 1] + grid[i+1][j] == 15)//i+1行
							&& (grid[i-1][j-1] + grid[i][j-1] + grid[i+1][j-1] == 15)//j-1列
							&& (grid[i-1][j+1] + grid[i][j+1] + grid[i+1][j+1] == 15)//j+1列
							&& ((grid[i - 1][j - 1] ^ grid[i - 1][j + 1] ^ grid[i - 1][j] ^ grid[i][j - 1]
									^ grid[i][j + 1] ^ grid[i + 1][j] ^ grid[i + 1][j - 1] ^ grid[i + 1][j + 1] ^ 1 ^ 2
									^ 3 ^ 4 ^ 6 ^ 7 ^ 8 ^ 9) == 0)) {
						cnt++;
					}
				}
			}
		}
		return cnt;
	}
    
}
